package targetToOffer.thrDay;

import javax.lang.model.type.ArrayType;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author Godc
 * @description 此题最主要要沟通是时间优先还是空间优先
 */
public class FindRepeatNumber {
    public static void main(String[] args) {
        FindRepeatNumberSolution s = new FindRepeatNumberSolution();
        int repeatNumber2 = s.findRepeatNumber2(new int[]{2, 3, 1, 0, 6, 5, 3});
        System.out.println(repeatNumber2);
    }
}
class FindRepeatNumberSolution {
    /**
     * 最简单的用Set集合
     * @param nums
     * @return
     */
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return nums[i];
            }
            set.add(nums[i]);
        }
        return 0;
    }

    /**
     * 空间o(1),注意题目中一个关键词在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
     * @param nums
     * @return
     */
    public int findRepeatNumber2(int[] nums) {
        int i = 0;
        while(i<nums.length){
            if(nums[i]==i){
                i++;
                continue;
            }
            if(nums[i]==nums[nums[i]]) return nums[i];
            int temp = nums[i];
            nums[i] = nums[nums[i]];
            nums[temp] = temp;
        }
        return -1;
    }

}
